package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/
@FunctionalInterface
public interface LetterCombinations {
    List<String> letterCombinations(String digits);
}

class LetterCombinationsImpl1 implements LetterCombinations{
    public static void main(String[] args) {
        new LetterCombinationsImpl1().letterCombinations("23");
    }


    static final char[] TWO = new char[]{'a','b','c'};
    static final char[] THREE = new char[]{'d','e','f'};
    static final char[] FOUR = new char[]{'g','h','i'};
    static final char[] FIVE = new char[]{'j','k','l'};
    static final char[] SIX = new char[]{'m','n','o'};
    static final char[] SEVEN = new char[]{'p','q','r','s'};
    static final char[] EIGHT = new char[]{'t','u','v'};
    static final char[] NINE = new char[]{'w','x','y','z'};
    static final char[][] CHAR_MAP = new char[][]{null,null,TWO,THREE,FOUR,FIVE,SIX,SEVEN,EIGHT,NINE};
    @Override
    @Deprecated
    /**
     * 写错了，当成全排列写了
     */
    public List<String> letterCombinations(String digits) {
        char[] charDigits = digits.toCharArray();
        boolean[] digitIsVisited = new boolean[digits.length()];
        List<String> ans = new LinkedList<>();
        char[] stack = new char[digits.length()];
        int top = 0;
        permuteDigit(charDigits,stack,digitIsVisited,ans,top);
        return ans;
    }
    private void permuteDigit(char[] digits,char[] stack,boolean[] digitIsVisited,List<String> ans,int top){
        if(top == digits.length){
            ans.add(String.valueOf(stack));
            return;
        }
        for (int i = 0; i < digits.length; i++) {
            if(!digitIsVisited[i]){
                char[] currentDigitMap = CHAR_MAP[digits[i] - '0'];
                digitIsVisited[i] = true;
                for (int j = 0; j < currentDigitMap.length; j++) {
                    stack[top++] = currentDigitMap[j];
                    permuteDigit(digits,stack,digitIsVisited,ans,top);
                    top--;
                }
                digitIsVisited[i] = false;
            }
        }
    }
}

class LetterCombinationsImpl2 implements LetterCombinations{
    static final char[] TWO = new char[]{'a','b','c'};
    static final char[] THREE = new char[]{'d','e','f'};
    static final char[] FOUR = new char[]{'g','h','i'};
    static final char[] FIVE = new char[]{'j','k','l'};
    static final char[] SIX = new char[]{'m','n','o'};
    static final char[] SEVEN = new char[]{'p','q','r','s'};
    static final char[] EIGHT = new char[]{'t','u','v'};
    static final char[] NINE = new char[]{'w','x','y','z'};
    static final char[][] CHAR_MAP = new char[][]{null,null,TWO,THREE,FOUR,FIVE,SIX,SEVEN,EIGHT,NINE};
    @Override
    public List<String> letterCombinations(String digits) {
        if("".equals(digits) || digits == null){
            return new ArrayList<>();
        }
        char[] charDigits = digits.toCharArray();
        char[] stack = new char[charDigits.length];
        int top = 0;
        List<String> ans = new LinkedList<>();
        letterCombinationsHelper(charDigits,stack,top,ans);
        return ans;
    }
    private void letterCombinationsHelper(char[] digits,char[] stack,int top,List<String> ans){
        if(top == stack.length){
            ans.add(String.valueOf(stack));
            return;
        }
        char currentDigit = digits[top];
        char[] currentCharMap = CHAR_MAP[currentDigit - '0'];
        for (int i = 0; i < currentCharMap.length; i++) {
            stack[top++] = currentCharMap[i];
            letterCombinationsHelper(digits,stack,top,ans);
            top--;
        }
        return;
    }
}